Efficient Alternative Route Planning in Road Networks

Abstract

Alternative route planning requires finding k alternative paths (including the shortest path) between a given source and target. These paths should be significantly different from each other and meaningful/natural (e.g., must not contain loops or unnecessary detours). While there exists many work on finding high-quality alternative paths, the existing techniques are computationally expensive and are unable to accommodate the high volume of queries required by modern navigation systems. To address this, in this paper, we propose an efficient approach to compute high-quality alternative paths. Our approach employs hub-labeling to efficiently identify candidate alternative paths. The candidate ..